package com.leetcode.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:给你两个整数left和right ，在闭区间 [left, right]范围内，统计并返回 计算置位位数为质数 的整数个数。
 *
 * 计算置位位数 就是二进制表示中 1 的个数。
 *
 * 例如， 21的二进制表示10101有 3 个计算置位。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/prime-number-of-set-bits-in-binary-representation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-04-05
 * Time:0:50
 */
public class Everyday762 {
    public int countPrime(int left,int right){
        int ans = 0;
        for (int x = left; x <= right; ++x) {
            if (((1 << Integer.bitCount(x)) & 665772) != 0) {/*我们可以用一个二进制数 \textit{mask}=665772=10100010100010101100_{2}mask=665772=10100010100010101100
                来存储这些质数，其中 \textit{mask}mask 二进制的从低到高的第 ii 位为 11 表示 ii 是质数，为 00 表示 ii 不是质数。
                设整数 xx 的二进制中 11 的个数为 cc，若 \textit{mask}mask 按位与 2^c不为 00，则说明 cc 是一个质数*/
                ++ans;
            }
        }
        return ans;
    }
    public int countPrimeSetBits(int left, int right) {
        int count = 0;
        for(int i = left;i <= right;i ++){
            if(isT(i)){
                count ++;
            }
        }
        return count;
    }
    public boolean isT(int x){
        String s = Integer.toBinaryString(x);
        int count = 0;
        for(int i = 0;i < s.length();i ++){
            if(s.charAt(i) == '1'){
                count ++;
            }
        }
        if(count == 1 || count ==0){
            return  false;
        }
        if(count == 2){
            return true;
        }
        for(int i = 2;i <= count / 2;i ++){
            if(count % i == 0){
                return false;
            }
        }
        return true;
    }
}
